package Hot_100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/*
    78. 子集 https://leetcode.cn/problems/subsets/
    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
*/

/*
    思路:这是一个组合问题:子集个数=C(n,0)+C(n,1)+C(n,2)+...+C(n,n)

*/
public class T78_subsets {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        backtracking(nums, 0);
        return result;
    }


//    从组合问题的角度去理解，有两种方案：选与不选，所以才有回溯的必要，递归出口就是当指针遍历完整个数组
    private void backtracking(int[] nums, int startIndex){
        result.add(new ArrayList<>(path)); //第一次进来的时候是空集
/*
        if (startIndex >= nums.length) {
            return;
        }
*/
        for (int i = startIndex; i < nums.length; i++) {
            //选
            path.add(nums[i]);
            backtracking(nums, i+1);

            //不选
            path.remove(path.size() - 1);
        }
    }

}
